package com.hackerrank.contests.oct13.challenges.period;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Solution {
	private static final int BASE = 5;
	private static final Surd ONE = new Surd(1, 0, BASE);
	/**
	 * Surd of the form a + b * sqrt(c), where a, b and c are integers
	 * @author naveen
	 */
	private static class Surd {
		int a, b, c;
		public Surd(int a, int b, int c) {
			this.a = a;
			this.b = b;
			this.c = c;
		}
		public boolean equals(Object s) {
			if(s instanceof Surd)
				return a == ((Surd)s).a && (b == ((Surd)s).b && c == ((Surd)s).c);
			return false;
		}
		/**
		 * Assumes this and s are similar surds otherwise product would not lead to a surd meaning c and s.c are same
		 * @param s surd to multiply this surd with
		 * @param m modulo with this number are taken for rational and irrational coefficients of the product
		 * @return product of this and s with rational and irrational coefficients taken modulo with m
		 */
		public Surd multiply(Surd s, int m) {
			return new Surd((a * s.a + c * b * s.b) % m, (a * s.b + b * s.a) % m, c);
		}
		public int hashCode() {
			return a + b * (int)Math.sqrt(c);
		}
		public String toString() {
			return a + " + " + b + " * sqrt(" + c + ")";
		}
	}
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int T = in.nextInt();
		for(int t = 0; t < T; t++) {
			int a = in.nextInt(), b = in.nextInt(), m = in.nextInt(), n = 1;
			Map<Surd, Surd> map = new HashMap<Surd, Surd>();
			Surd s = new Surd(a, b, BASE), p = new Surd(a, b, BASE);
			while(!p.equals(ONE) && !map.containsKey(p)) {
				Surd np = p.multiply(s, m);
				n++;
				map.put(p, np);
				p = np;
			}
			if(map.containsKey(p))
				System.out.println(-1);
			else
				System.out.println(n);
		}
	}
}
